package backtrack;

public class Ex200 {
    static class Solution {
        int[][] flag;
        char[][] grid;
        int m, n;
        public int numIslands(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            this.grid = grid;
            this.flag = new int[m][n];
            int count = 0;
            this.m = m;
            this.n = n;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1' && flag[i][j] == 0) {
                        dfs (i, j);
                        count++;
                    }
                }
            }
            return count;
        }

        public void dfs (int i, int j) {
            if (!isInArea(i, j) || flag[i][j] == 1 || grid[i][j] == '0') return;
            flag[i][j] = 1;
            dfs(i + 1, j);
            dfs(i - 1, j);
            dfs(i, j - 1);
            dfs(i, j + 1);
        }

        public boolean isInArea(int i, int j) {
            return i >= 0 && i < m && j >= 0 && j < n;
        }
    }
}
